package leetcode.p1019;

public class NextGreaterNodeInLinkedList {
    public static void main(String[] args) {
        ListNode head = new ListNode(2);
        ListNode tmp = head;
        tmp.next = new ListNode(7); tmp = tmp.next;
        tmp.next = new ListNode(4); tmp = tmp.next;
        tmp.next = new ListNode(3); tmp = tmp.next;
        tmp.next = new ListNode(5); tmp = tmp.next;
        int[] ints = new NextGreaterNodeInLinkedList().nextLargerNodes(head);
        for (int i = 0; i < ints.length; i++) System.out.print(ints[i] + ", ");
        System.out.println();
    }
    public int[] nextLargerNodes(ListNode head) {
        //先遍历一遍获取List长度，试过几次，使用List动态赋值，内存及耗时要比先读一遍长度new数组要大
        ListNode root = head;
        int len = 0;
        while (root != null) {
            root = root.next;
            len++;
        }
        //sta[i][0] 记录下标，sta[i][1] 记录值
        int[][] sta = new int[len][2];
        //答案数组
        int[] result = new int[len];
        int tail = -1;
        int i = 0;
        while (head != null) {
            //维护单调递减栈，保证sta数组中的值是递减的
            while (tail != -1 && sta[tail][1] < head.val) {
                //每弹出一个值就可以更新一次答案数组
                result[sta[tail][0]] = head.val;
                tail--;
            }
            //初始不知道后面是否有比它大的值，故值为0
            result[i] = 0;
            //head.val的值比sta栈顶值要小，将其加入sta
            sta[++tail][0] = i++;
            sta[tail][1] = head.val;
            head = head.next;
        }
        return result;
    }
}

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) {this.val = val;}
    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}
